<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3613：[Heoi2014]南园满地堆轻絮</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Heoi2014]南园满地堆轻絮</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Heoi2014]南园满地堆轻絮</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Heoi2014]南园满地堆轻絮                </h1>
                <p>时间限制：50s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：256MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>小 Z 是 ZRP（Zombies&rsquo; Republic of Poetry，僵尸诗歌共和国）的一名诗歌爱好者，最近 他研究起了诗词音律的问题。</div>
<div>&nbsp; 在过去，诗词是需要编成曲子唱出来的，比如下面这首《菩萨蛮》，唱出来的话其对应 的音符就是这样的：</div>
<div>&nbsp; &nbsp;南 &nbsp;园 &nbsp;满 地 堆 轻 絮， 愁 闻 一 霎 清 明 雨</div>
<div>&nbsp; &nbsp;1 &nbsp; 1 &nbsp;5 5 6 6 5 &nbsp;4 4 3 3 2 2 1 &nbsp;</div>
<div>因而可以发现，&ldquo;1 1 5 5 6 6 5 4 4 3 3 2 2 1&rdquo;这串音符就成为了研究音律的关键。</div>
<div>&nbsp;小 Z 翻阅了众多史料发现，过去的一首曲子的音调是不下降的&nbsp;</div>
<div>&nbsp;小 Z 想要知道对于一首给定的曲子，如何通过提高音调或者降低音调，将它的音调修改 的不下降，</div>
<div>而且使得修改幅度最大的那个音符的修改幅度尽量小。</div>
<div>即如果把一个包含 n 个音 符的曲子看做是一个正整数数列 A[1]&hellip;A[n]，</div>
<div>那么 目标是求另一个正整数数列 B[1]&hellip;B[n]， 使得对于任意的 1&le;i&lt;n 有 B[i] &le;B[i+1]，</div>
<div>而且使得 Ans = Max{|A[j]-B[j]|,1&le;j&le;n}尽量 小。 &nbsp;小 Z 很快就想清楚了做法，但是鉴于他还忙着写诗，</div>
<div>所以这个任务就交给了你。&nbsp;</div>
<div></div></p><hr/><h3>输入格式</h3><p><p>由于数据规模可能较大，因此采用如下方式生成数据。</p>
<div>
<div>&nbsp;每个数据包含 6 个数：n,Sa,Sb,Sc,Sd,A[1],Mod,意为共有 n 个音符，第一个音符为 A[1]。</div>
<div>&nbsp;生成规则如下： 定义生成函数 F(x) = Sa*x^3 + Sb*x^2 + Sc*x + Sd;&nbsp;</div>
<div>那么给出递推公式 A[i] = F(A[i-1]) + F(A[i-2])，此处规定 A[0] = 0.&nbsp;</div>
<div>由于中间过程的数可能会特别大，所以要求每一步与 A 中的每个数都对一个给定的数 Mod 取模。</div>
<div></div>
</div></p><hr/><h3>输出格式</h3><p><p>输出一行，包含一个正整数 Ans。&nbsp;</p>
<div>
<div></div>
</div></p><hr/><h3>样例输入</h3><pre>3 815 6901 3839 178 199 10007 </pre><hr/><h3>样例输出</h3><pre>1334</pre><hr/><h3>提示</h3><p><p>&nbsp; n&le;5000000&nbsp;</p>
<div>对于 100%的数据, Sa,Sb,Sc,Sd,A[1] &le;10000, Mod&le;1000000007&nbsp;</div>
<div></div>
<div>样例中生成的数列为： &nbsp;</div>
<div>199 4568 1901，此时将 4568 修改为 3234,1901 也修改为 3234 即可，代价为 1334。&nbsp;</div></p><hr/><h3>题目来源</h3><p>鸣谢佚名上传</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3613" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3613" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>